package org.niu.array;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class ScheduleCourse {
    public int scheduleCourse(int[][] courses) {
        // 1.贪心先选最早结束的
        // 2.当课程数量相同时，选持续时间最短的
        Arrays.sort(courses, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int total = 0;
        for (int[] course : courses) {
            int duration = course[0],last = course[1];
            if (total+duration<=last){
                total+=duration;
                q.offer(duration);
            }
            // 如果里面的dur比外面的持续时间长，我是不能容忍的，减去两者之差
            else if(!q.isEmpty() && q.peek() > duration){
                total -= q.poll() - duration;
                q.offer(duration);
            }
        }
        return q.size();

    }
}
